# 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重
# 复的三元组。
#
#  注意：答案中不可以包含重复的三元组。
#
#
#
#  示例 1：
#
#
# 输入：nums = [-1,0,1,2,-1,-4]
# 输出：[[-1,-1,2],[-1,0,1]]
#
#
#  示例 2：
#
#
# 输入：nums = []
# 输出：[]
#
#
#  示例 3：
#
#
# 输入：nums = [0]
# 输出：[]
#
#
#
#
#  提示：
#
#
#  0 <= nums.length <= 3000
#  -105 <= nums[i] <= 105
#
#  Related Topics 数组 双指针 排序
#  👍 3759 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        result = []
        for first in range(n):
            if first > 0 and nums[first] == nums[first-1]:
                continue
            target = - nums[first]
            third = n - 1
            for second in range(first + 1, n):
                if second > first + 1 and nums[second] == nums[second-1]:
                    continue
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    result.append([nums[first], nums[second], nums[third]])
        return result






# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


"""
排序 + 双指针
避免a, b,c 重复: a > b > c
避免相邻元素重复: 循环时跳到下一个不同元素
b 增大时需要c减小, 故从小到大遍历b, 从大到小遍历c
双指针, 一个元素递增, 一个元素递减
"""
#     def threeSum(self, nums: List[int]) -> List[List[int]]:
#         n = len(nums)
#         nums.sort()
#         result = list()
#
#         for first in range(n):
#             # 第一层循环跳过相同元素
#             if first > 0 and nums[first] == nums[first - 1]:
#                 continue
#             # c 从右到左
#             third = n - 1
#             target = -nums[first]
#             # 二层循环枚举b
#             for second in range(first + 1, n):
#                 # 二层过滤跳过相同元素
#                 if second > first + 1 and nums[second] == nums[second - 1]:
#                     continue
#                 # 第三层循环左移减小
#                 while second < third and nums[second] + nums[third] > target:
#                     third -= 1
#                 # 相等如果继续下次循环, 会指针交错, 不满足 b < c
#                 if second == third:
#                     break
#                 if nums[second] + nums[third] == target:
#                     result.append([nums[first], nums[second], nums[third]])
#         return result


if __name__ == '__main__':
    s = Solution()
    nums = [-1, 0, 1, 2, -1, -4]
    r = s.threeSum(nums)
    # [[-1,-1,2],[-1,0,1]]
    assert r == [[-1, -1, 2], [-1, 0, 1]], r
